Data storage devices (e.g., disk drives or non-volatile semiconductor memories) may be employed as mass storage for a computer system (e.g., desktop, laptop, portable, etc.) or a consumer device (e.g., music player, cell phone, camera, etc.) or other suitable application. The data storage device includes a non-volatile memory (e.g., a disk or a semiconductor memory) for storing user data in blocks which are accessed using an address translation layer. For example, the address translation layer may map a logical block address (LBA) received from a host to a physical block address (PBA) representing a segment of the non-volatile memory. The indirect mapping of LBA to PBA facilitates aspects such as defect mapping, and log-structured file systems where the LBA to PBA mapping may change over time.
An example data storage device employing an address translation layer is a non-volatile semiconductor memory comprising one or more memory devices (such as a flash memory). Each memory device typically comprises a number of blocks which are accessed a page at a time. For example, a single block may comprise 128 pages where each page comprises 4096 bytes. Since a page typically cannot be overwritten without first being erased, a new page in a different block is typically selected to perform an “overwrite” operation. Accordingly, the address translation layer must maintain the appropriate LBA to PBA mapping as each write operation changes the physical location of the user data (similar to a log-structured file system).
When a data storage device is powered on, it typically loads a LBA to PBA mapping table from the non-volatile memory into a volatile memory (DRAM or SRAM) for on-the-fly mapping of LBAs to PBAs when performing access operations. It is desirable to minimize the size of the mapping table in order to reduce the size (and cost) of the volatile memory needed to store the mapping table.